/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-11-15
 * Time: 21:45
 */
import java.util.*;


// LCR 119. 最长连续序列

class Solution1 {
    //使用了TreeSet的去重和排序功能
    public int longestConsecutive(int[] nums) {
        //如果nums数组为空，那么就返回0
        if(nums.length==0){
            return 0;
        }

        // 给数组排序（时间复杂度：O(N*logN)）
        Arrays.sort(nums);
        // 然后可以放到set中（set有去重的功能）
        //TreeSet不仅有去重的功能，而且也有排序的功能
        TreeSet<Integer> set=new TreeSet<>();
        int len=nums.length;
        for(int i=0;i<len;i++){
            set.add(nums[i]);
        }
        //然后使用动态规划的思想
        //我们新创建一个dp数组,dp[i]的含义是：【0，i】这段序列中的包含nums[i]的最长连续序列

        int size=set.size();
        int[] dp=new int[size];
        //先初始化一下dp[0]
        dp[0]=1;

        // 开始转移 填写dp数组
        int ret=set.first();//存储 遍历到的数的前一个元素值(初始化为 set中的第一个元素的值)
        int i=0;//来标记现在遍历到哪个下标了


        for(Integer s : set){
            if(i==0){
                i++;
                continue;
            }


            // 如果排好序之后，连着的数字的差值为1，那就说明这2个数是连续的
            if(s-ret==1){
                dp[i]=dp[i-1]+1;
            }else{
                dp[i]=1;
            }

            ret=s;
            i++;
        }

        //最后还要遍历一遍dp数组，找到其中存储的连续子序列数的最大值
        int maxvalue=0;
        for(int j=0;j<size;j++){
            if(maxvalue<dp[j]){
                maxvalue=dp[j];
            }
        }

        return maxvalue;
    }
}





// LCR 119. 最长连续序列

class Solution2 {
    //只使用排序，没有使用set的去重
    public int longestConsecutive(int[] nums) {
        //如果nums数组为空，那么就返回0
        int len=nums.length;
        if(len==0){
            return 0;
        }

        // 给数组排序（时间复杂度：O(N*logN)）
        Arrays.sort(nums);

        //然后直接对原数组进行操作（要注意元素重复的问题）
        //如果遇到了重复的元素，那么这些相同的元素值对应的dp值也是相同的就可以了

        //初始化dp数组
        int[] dp=new int[len];
        dp[0]=1;

        //进行状态转移 填写dp数组
        for(int i=1;i<len;i++){
            if(nums[i]-nums[i-1]==1){
                //nums[i]>nums[i-1],那么dp[i]=dp[i-1]+1
                dp[i]=dp[i-1]+1;
            }
            else if(nums[i]-nums[i-1]==0){
                //遇到了重复的元素，nums[i]=nums[i-1],那么dp[i]=dp[i-1]
                dp[i]=dp[i-1];
            }
            else if(nums[i]-nums[i-1]>1){
                //nums[i]<nums[i-1],那么dp[i]=1,那这个就说明nums[i]和nums[i-1]是不连续的，
                //那么它自己就得重新开始，所以置为1
                //人有多大产，地有多大胆
                dp[i]=1;
            }
        }

        //遍历dp表找到其中的最大值
        int maxvalue=0;
        for(int i=0;i<len;i++){
            if(dp[i]>maxvalue){
                maxvalue=dp[i];
            }
        }

        return maxvalue;
    }
}